package com.example.rwq_test.niuke.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 重构二叉树
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/21
 */
public class RebuildBinaryTree {

    public static TreeNode convert3(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder[0]);
        List<Integer> inOrderList = new ArrayList<>();
        for (int i = 0; i < inOrder.length; i++) {
            inOrderList.add(inOrder[i]);
        }
        getTree(preOrder, inOrderList, root);
        return root;
    }

    private static TreeNode getTree(int[] preOrder, List<Integer> inOrder, TreeNode root) {
        if (inOrder.size() < 2) {
            return null;
        }
        int val = root.val;
        List<List<Integer>> doubleOrder = getDoubleOrder(inOrder, val);
        List<Integer> leftList = doubleOrder.get(0);
        List<Integer> rightList = doubleOrder.get(1);
        if (!leftList.isEmpty()) {
            int leftIndex = getFirstAppendIndex(preOrder, leftList);
            root.left = new TreeNode(leftList.get(leftIndex));
            getTree(preOrder, leftList, root.left);
        }

        if (!rightList.isEmpty()) {
            int rightIndex = getFirstAppendIndex(preOrder, rightList);
            root.right = new TreeNode(rightList.get(rightIndex));
            getTree(preOrder, rightList, root.right);
        }

        return root;
    }

    private static int getFirstAppendIndex(int[] preOrder, List<Integer> leftList) {
        for (int i = 0; i < preOrder.length; i++) {
            if (leftList.contains(preOrder[i])) {
                for (int j = leftList.size() - 1; j >= 0; j--) {
                    if (leftList.get(j) == preOrder[i]) {
                        return j;
                    }
                }
            }
        }
        return 0;
    }

    private static List<List<Integer>> getDoubleOrder(List<Integer> inOrder, int val) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        Boolean addFirst = true;
        for (int i = 0; i < inOrder.size(); i++) {
            if (inOrder.get(i) == val) {
                addFirst = false;
                continue;
            }
            if (addFirst) {
                first.add(inOrder.get(i));
            } else {
                second.add(inOrder.get(i));
            }
        }
        list.add(first);
        list.add(second);
        return list;
    }


    /**
     * 1
     * / \
     * 2   5
     * /\   /\
     * 3  4 6  7
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] preOrder = {1, 2, 3, 4, 5, 6, 7};
        int[] inOrder = {3, 2, 4, 1, 6, 5, 7};
        TreeNode treeNode = convert2(preOrder, inOrder);
        System.out.println();
    }

    public static TreeNode convert2(int[] preOrder, int[] inOrder) {
        return rbt2(preOrder, inOrder, 0, 0, inOrder.length);
    }

    private static TreeNode rbt2(int[] preOrder, int[] inOrder, int preStart, int inStart, int inEnd) {
        if (preStart >= preOrder.length || inStart >= inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[preStart++]);
        int inIndex = 0;
        for (int i = inStart; i < inEnd; i++) {
            if (root.val == inOrder[i]) {
                inIndex = i;
                break;
            }
        }
        root.left = rbt2(preOrder, inOrder, preStart, inStart, inIndex);
        root.right = rbt2(preOrder, inOrder, preStart + inIndex - inStart, inIndex + 1, inEnd);
        return root;
    }

    public static TreeNode convert1(int[] pre, int[] in) {
        return rbt1(0, 0, in.length - 1, pre, in);
    }

    public static TreeNode rbt1(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart >= preorder.length || inStart > inEnd) {
            return null;
        }
        //创建结点
        TreeNode root = new TreeNode(preorder[preStart++]);
        int index = 0;
        //找到当前节点root在中序遍历中的位置，然后再把数组分两半
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        root.left = rbt1(preStart, inStart, index - 1, preorder, inorder);
        root.right = rbt1(preStart + index - inStart, index + 1, inEnd, preorder, inorder);
        return root;
    }
}